/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/02
 */
package CodingTest.AC20190302;

public class countBits {
    //方法一：时间复杂度：O(n*sizeof(integer))
    public int[] countBits(int num){
        int[] res = new int[num+1];
        for(int i =0;i<=num;i++){
            int count = 0;
            int a = i;
            while(a != 0){
                if(a%2 ==1)count ++;
                a = a/2;
            }
            res[i] = count;
        }
        return res;
    }
    //方法二：
//    对于求解一个十进制数转化为二进制时里面1的个数，可以先看一下概况：
//
//    十进制数　　　　　　　　二进制数　　　　　　　　1的个数
//
//　　1　　　　　　　　　　　　1　　　　　　　　　　   1
//
//        　　2　　　　　　　　　　　　10　　　　　　　　　　 1
//
//        　　3　　　　　　　　　　　　11　　　　　　　　　　  2
//
//        　　4　　　　　　　　　　　　100　　　　　　　　　　1
//
//        　　5　　　　　　　　　　　　101　　　　　　　　　　 2
//
//        　　6　　　　　　　　　　　　110　　　　　　　　　　  2
//
//        　　7　　　　　　　　　　　　111　　　　　　　　　　  3
//
//
//
//    看上面的一系列数字的二进制中1的个数：
//
//    对于一个偶数 n ；其二进制组成最低位为0，所以其1的位数就是除了最低位之外前面那一部分中1的位数，即是i/2中1的位数。
//
//    对于一个奇数n，其末位的数一定是1，那么对于n-1，一定是个偶数，并且只需要将n-1的末位0改成1就可以变成 n，因为   a[n] = a[n - 1] +1;
//
//    则可以得出上面两个递推关系式。
//
//    按照动态规划的思路：
//
//            1：问题归纳：用数组a[ i ] 表示 i 的二进制中1的个数。
//
//            2：递推关系式　　　　a[n] = a[n/2]     　　　　　　n为偶数
//
//　　　　　　　　　　a[n] = a[n-1] +1　　　　　　 n为奇数
//
//              3：初始化：a[0] = 0
    public int[] countBits2(int num){
        int[] res = new int[num+1];
        res[0] = 0;
        int n = num%2 != 0 ? num-1:num;
        for(int i =1;i<=num;i++){
            res[i] = res[i-1] +1;
            i++;
            res[i] = res[i/2];
        }
        if(num%2 != 0){
            res[num] = res[n]+1;
        }
        return res;
    }
//    方法三：
    public static void main(String[] args) {
        countBits cb = new countBits();
        System.out.println(cb.countBits(5));
    }
}
